#include <algorithm>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
  vector<int> findAnagrams(string s, string p) {
    int s_length = s.length();
    int p_length = p.length();
    if (s_length < p_length) {
      return {};
    }
    vector<int> res;
    // 窗口中各字母出现次数
    vector<int> sCount(26, 0);
    // s中各字母出现次数
    vector<int> pCount(26, 0);
    for (int i = 0; i < p_length; i++) {
      pCount[p[i] - 'a']++;
      sCount[s[i] - 'a']++;
    }
    if (pCount == sCount) {
      res.push_back(0);
    }
    // 滑动窗口
    for (int i = 0; i < s_length - p_length; i++) {
      // 窗口右移
      sCount[s[i] - 'a']--;
      sCount[s[i + p_length] - 'a']++;
      if (sCount == pCount) {
        // 当前窗口开始位置为: i+1
        res.push_back(i + 1);
      }
    }
    return res;
  }
};